/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        538.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 21:46
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给出二叉 搜索 树的根节点，该树的节点值各不相同，
// 请你将其转换为累加树（Greater Sum Tree），
// 使每个节点 node的新值等于原树中大于或等于node.val的值之和。
//
//提醒一下，二叉搜索树满足下列约束条件：
//
//节点的左子树仅包含键 小于 节点键的节点。
//节点的右子树仅包含键 大于 节点键的节点。
//左右子树也必须是二叉搜索树。
#include "../header.h"
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }

private:
    int ans = 0;
    void traverse(TreeNode *root){
        if (root == nullptr)
            return;
        traverse(root->right);
        ans += root->val;
        root->val = ans;
        traverse(root->left);
    }
};
